package com.acyouzi.leetcode.dp;

import java.util.Arrays;

/**
 * 17/9/26 21:38
 *
 * @author sunxu
 */
public class PartitionEqualSum {
  public boolean canPartition(int[] nums) {
    int sum = Arrays.stream(nums).reduce((x,y) -> x+y).getAsInt();
    if (sum % 2 != 0) return false;
    sum /= 2;
    boolean[] dp = new boolean[sum+1];
    dp[0] = true;
    for (int i : nums){
      for (int j = sum; j >= i; j--) {
        dp[j] = dp[j] || dp[j - i];
      }
    }
    return dp[sum];
  }
}
